package com.aurora.leetcode.answer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author : Aurora
 * @date : 2024/3/28 11:46
 * @description
 *  假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *  每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 */
public class ClimbStairs_70 {

    private static int method = 0;


    //当n=36时，超出时间限制
    public  int climbStairs1(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        return climbStairs1(n-1) + climbStairs1(n-2);
    }

    /**
     * 递归方法改进-使用备忘录思想
     * @param n
     * @return
     */
    private Map<Integer, Integer> map = new HashMap<>();
    public  int climbStairs2(int n){
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        Integer oneStep = map.get(n - 1);
        Integer twoStep = map.get(n-2);
        if(oneStep == null){
            oneStep = climbStairs2(n-1);
            map.put(n-1, oneStep);
        }
        if(twoStep == null){
            twoStep = climbStairs2(n-2);
            map.put(n-2, twoStep);
        }
        return oneStep+twoStep;
    }
    public  int climbStairs2_1(int n){
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(map.get(n) != null){
            return map.get(n);
        }
        map.put(n, climbStairs2_1(n-1)+climbStairs2_1(n-2));
        return map.get(n);
    }

    public int climbStair2_2(int n){
        Integer[] result = new Integer[n+1];
        return climbStairs22(n, result);
    }
    public int climbStairs22(int n, Integer[] result){
        if(result[n] > 0){
            return result[n];
        }
        if(n == 1) return 1;
        if(n == 2) return 2;
        return result[n]=climbStairs22(n-1,result)+climbStairs22(n-2,result);
    }

    public static void main(String[] args) {
        ClimbStairs_70 climbStairs70 = new ClimbStairs_70();

//        Long oneS = System.currentTimeMillis();
//        int method1 = climbStairs70.climbStairs1(45);
//        Long oneE = System.currentTimeMillis();
//        System.out.println("执行结果1："+method1+"  耗时："+(oneE - oneS)/1000);
//
//        Long startTimeTwo = System.currentTimeMillis();
//        int method2 = climbStairs70.climbStairs2(45);
//        Long endTimeTwo = System.currentTimeMillis();
//        System.out.println("执行结果2："+method2+"  耗时："+(endTimeTwo - startTimeTwo)/1000);

        Long startTimeTwo2_1 = System.currentTimeMillis();
        int method2_1 = climbStairs70.climbStairs2_1(45);
        Long endTimeTwo2_1 = System.currentTimeMillis();
        System.out.println("执行结果2-1："+method2_1+"  耗时："+(endTimeTwo2_1 - startTimeTwo2_1)/1000);

    }

}
